Nowadays, with the development of network communication and electronic commerce, security ensuring in communication has become an important issue. One method for ensuring security is cryptographic technology, and communication using various encryption techniques is currently done in actuality.
For example, a system has been put into practical use in which a cryptographic processing module is embedded in a compact device such as an IC card to perform data transmission and reception between the IC card and a reader/writer serving as a data reading and writing apparatus to perform authentication processing or encryption and decryption of transmission and reception data.
There are various cryptographic processing algorithms, which are broadly classified into a public key cryptographic scheme in which an encryption key and a decryption key are set as different keys, for example, a public key and a private key, and a common key cryptographic scheme in which an encryption key and a decryption key are set as a common key.
The common key cryptographic scheme has various algorithms, one of which is a scheme in which a plurality of keys are generated based on a common key and data transformation processing in units of a block (such as 64-bit or 128-bit) is repeatedly executed using the plurality of generated keys. A typical algorithm with the application of such a key generation scheme and data transformation processing is a common key block cipher scheme.
As typical algorithms for common key block ciphers, for example, the DES (Data Encryption Standard) algorithm, which was formerly the U.S. standard cryptography, the AES (Advanced Encryption Standard) algorithm, which is the current U.S. standard cryptography, etc., have been known.
Such algorithms for common key block ciphers are mainly constituted by round function sections having F-function sections that repeatedly execute the transformation of input data, and a key scheduling section that generates round keys to be applied in the F-function sections in respective rounds of the round function sections. The key scheduling section first increases the number of bits to generate an expanded key on the basis of a master key (main key), which is a private key, and generates, on the basis of the generated expanded key, round keys (sub-keys) to be applied in the F-function sections in the respective rounds of the round function sections.
A known specific structure that executes an algorithm to which such round functions (F functions) are applied is a Feistel structure. The Feistel structure has a structure that transforms plaintext into ciphertext by using simple repetition of round functions (F-functions) serving as data transformation functions. Examples of documents describing cryptographic processing with the application of the Feistel structure include Non-Patent Documents 1 and 2.
However, problems of common key block cipher processing to which the Feistel structure is applied involve leakage of keys due to cryptanalysis. Typical known techniques of cryptanalysis or attack techniques include differential analysis (also called differential cryptanalysis or differential attack) in which multiple pieces of input data (plaintext) having certain differences therebetween and output data (ciphertext) thereof are analyzed to analyze applied keys in respective round functions, and linear analysis (also called linear cryptanalysis or linear attack) in which analysis based on plaintext and corresponding ciphertext is performed.
Easy analysis of keys due to cryptanalysis implies low security of the cryptographic processing therefor. In cryptographic algorithms of the related art, since processes (transformation matrices) applied in linear transformation sections of round function (F-function) sections are equal to each other in rounds of respective stages, analysis is feasible, resulting in easy analysis of keys.
As a configuration to address such a problem, a configuration in which two or more different matrices are arranged in linear transformation sections of round function (F-function) sections in a Feistel structure so that the matrices are switched every round has been proposed. This technology is called a diffusion-matrix switching mechanism (DSM: Diffusion Switching Mechanism, hereinafter referred to as DSM). This DSM enables enhancement of resistance to differential attacks or linear attacks.
FIG. 1 shows an example of a cryptographic processing configuration in which, instead of applying a diffusion-matrix switching mechanism (DSM), a Feistel structure of the related art in which only one type of matrix is arranged in linear transformation sections of round function (F-function) sections in a Feistel structure is applied. In the Feistel structure shown in FIG. 1, the number of rounds is set to r (for example, r=16), and F-functions in the respective rounds are indicated by F. The input is plaintext P. The plaintext P is divided into two data lines P[0] and P[1] (the number of divisions=2), and data transformation with the application of the F-functions is sequentially executed in the respective rounds to output C[0] and C[1], which constitute ciphertext C, as results of the transformation for the r rounds. In the F-functions for the respective rounds, round keys (sub-keys) serving as elements constituting an expanded key generated on the basis of a master key (main key) supplied from a key scheduling section, which is not shown in the figure, are input and applied for data transformation.
In the configuration shown in FIG. 1, the n-bit plaintext P is processed r times (r stages) using F-functions to which round keys RK1, RK2, . . . , RKr are input, and, as a result, the n-bit ciphertext C is obtained. Halves into which the plaintext P is divided are respectively represented by P[0] and P[1] (P=P[0]∥P[1]). Note that X1∥X2 denotes concatenation data of X1 and X2. Likewise, halves into which the ciphertext C is divided are also respectively called C[0] and C[1] (C=C[0]∥C[1]). Note that the detailed configuration of the F-functions are described in detail in the section of the explanation of the present invention.
In this manner, in a configuration in which respective rounds have F-functions of the same form to which a common linear transformation matrix is applied, in a case where decryption processing of returning ciphertext into plaintext is performed, as shown in FIG. 2, a Feistel structure having completely the same configuration is applied, and it is only required to set the order of round keys applied in respective rounds to be opposite to that in the case of the encryption processing. That is, it is possible to apply completely the same function to both an encryption function and a decryption function. In this manner, if it is possible to apply the same function to encryption processing and decryption processing, in view of implementation, a single configuration can be shared between encryption processing and decryption processing in hardware or software. Thus, size reduction and cost reduction of an apparatus are achieved. Note that in a case where it is possible to apply a common function to an encryption function and a decryption function, a corresponding cipher is defined to have involution properties.
This means that when an encryption function E that encrypts plaintext P using round keys RK1, RK2, . . . , RKr is represented by E(P, RK1, RK2, . . . , RKr), and a decryption function D that decrypts ciphertext C using round keys RK1, RK2, . . . , RKr is represented by D(C, RK1, RK2, . . . , RKr), the following representations are given:
      (          encryption      ⁢                          ⁢      function        )        C    =          E      ⁡              (                  P          ,                      RK            1                    ,                      RK            2                    ,          …          ⁢                                          ,                      RK            r                          )                  (          decryption      ⁢                          ⁢      function        )                                P          =                    ⁢                      D            ⁡                          (                              C                ,                                  RK                  1                                ,                                  RK                  2                                ,                …                ⁢                                                                  ,                                  RK                  r                                            )                                                                    =                    ⁢                      E            ⁡                          (                              C                ,                                  RK                  r                                ,                                  RK                                      r                    -                    1                                                  ,                …                ⁢                                                                  ,                                  RK                  1                                            )                                          
It is found from above that the decryption function D is equivalent to the encryption function E, where the order of the round keys is permuted.
FIG. 3 shows an example of a Feistel structure including a diffusion-matrix switching mechanism (DSM) in which two or more different matrices are arranged in linear transformation sections of round function (F-function) sections in the Feistel structure so that the matrices are switched every round. The Feistel structure shown in FIG. 3 is configured such that, as in that of FIG. 1, the number of rounds is set to r (for example, r=16).
In the present example configuration, the F-functions in the respective rounds are configured such that a diffusion-matrix switching mechanism (DSM) configured to arrange two different F-functions F0 and F1 according to a certain rule is applied to improve resistance to differential attacks or linear attacks. That is, the F-functions F0 and F1 are configured to execute data transformation to which different linear transformation matrices are applied.
The input is plaintext P. The plaintext P is divided into two data lines P[0] and P[1] (the number of divisions=2), and data transformation with the application of the F-functions is sequentially executed in the respective rounds to output C[0] and C[1], which constitute ciphertext C, as results of the transformation for the r rounds. In the F-functions F0 and F1 for each round, round keys (sub-keys) serving as elements constituting an expanded key generated on the basis of a master key (main key) supplied from a key scheduling section, which is not shown in the figure, are input and applied to data transformation.
In a Feistel structure with the application of such a diffusion-matrix switching mechanism (DSM), in a case where decryption processing for returning ciphertext into plaintext is performed, as shown in FIG. 4, it is possible to perform the decryption processing by, without modifying the arrangement of the F-functions F0 and F1 for the respective rounds, using a Feistel structure to which a DSM having the same configuration as that of FIG. 3 is applied and setting the order of round keys applied to the respective rounds to be opposite to that of the encryption processing. That is, involution properties that enable a common function to be applied to an encryption function and a decryption function are also held in a Feistel structure to which a diffusion-matrix switching mechanism (DSM) is applied.
In a Feistel structure having the diffusion-matrix switching mechanism (DSM) explained with reference to FIGS. 3 and 4, plaintext P as the input is divided into two data lines P[0] and P[1], which are then input to round function sections to generate ciphertext. Alternatively, a configuration is provided in which ciphertext C is divided into two data lines C[0] and C[1], which are then input to round function sections to generate decrypted text. The number of data divisions is called the number of data lines or the number of divisions. A Feistel structure having the diffusion-matrix switching mechanism (DSM) shown in FIGS. 3 and 4 has a structure with the number of data lines (the number of divisions)=2. In the case of such a structure with the number of data lines (the number of divisions)=2, by suitably arranging F-functions, a configuration that allows the involution properties to be held can be built.
Unlike such a Feistel structure having only two data lines, on the other hand, an extended Feistel structure (GFN: Generalized Feistel Network) in which an arbitrary number of data lines greater than or equal to 3, for example, 3, 4, 5 . . . etc., are allowed exists. That is, a configuration exists in which the number of data lines on the input is not limited to two and three or more data lines are commonly used.
In an extended Feistel structure (GFN), a configuration in which, for example, plaintext P is divided into three data lines P[0], P[1], and P[2], which are then input to round function sections, or is divided into four data lines P[0], P[1], P[2], and P[3], which are then input to round function sections, or the like is allowed. Such a Feistel structure with an arbitrary number of data lines (the number of divisions) greater than or equal to 3 is called an extended Feistel structure (GFN: Generalized Feistel Network).
In such an extended Feistel structure (GFN) having an arbitrary number of data lines greater than or equal to 3, it is difficult to provide a configuration that holds the involution properties described above, that is, involution properties that allow a common function to be applied to an encryption function and a decryption function. In an extended Feistel structure (GFN), furthermore, it is further difficult to provide a configuration that holds involution properties in a configuration to which the diffusion-matrix switching mechanism (DSM) described above is applied, that is, a DSN-applied configuration having a configuration in which transformation processes in F-functions for respective rounds are not uniform.    Non-Patent Document 1: K. Nyberg, “Generalized Feistel networks”, ASIACRYPT'96, SpringerVerlag, 1996, pp. 91-104.    Non-Patent Document 2: EYuliang Zheng, Tsutomu Matsumoto, Hideki Imai: On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses. CRYPTO 1989: 461-480